package nl.utwente.eemcs.common.analysis;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingDeque;

import nl.utwente.eemcs.graph.Edge;
import nl.utwente.eemcs.graph.EdgeType;
import nl.utwente.eemcs.graph.Graph;
import nl.utwente.eemcs.graph.LoopConditionalNode;
import nl.utwente.eemcs.graph.LoopConstruct;
import nl.utwente.eemcs.graph.Node;

public class LoopConstructAnalyzer2 {

	private BlockingQueue<Graph> graphQueue = new LinkedBlockingDeque<Graph>();
	private Graph inputGraph;
	
	/**
	 * Create a new instance of a loop construct analyzer
	 * @param inputGraph The input graph
	 */
	private LoopConstructAnalyzer2(Graph inputGraph) {
		this.inputGraph = inputGraph;
	}
	
	/**
	 * Analyze the graph and create loop constructs
	 * @param inputGraph Input graph
	 * @return Changed input graph
	 * @throws Exception When an error occurs during the transformation, an exception will be thrown
	 */
	public static Graph analyze(Graph inputGraph) throws Exception {
		LoopConstructAnalyzer2 analyzer = new LoopConstructAnalyzer2(inputGraph);
		return analyzer.analyze();
	}
	
	/**
	 * Analyze graph and replace loopconstructs
	 * @return The input graph is returned, with the changes that were made by this algorithm
	 * @throws Exception When an error occurs during the transformation, an exception will be thrown
	 */
	private Graph analyze() throws Exception {
		// Add all graph/subgraphs to 
		for (Graph g : inputGraph.getAllGraphsAndSubGraphs())
			graphQueue.add(g);
		
		while (!graphQueue.isEmpty()) {
			Graph g = graphQueue.take();
			List<LoopConditionalNode> loopNodes = findLoopNodes(g);
			
			// Take first loop node
			if (loopNodes.size() > 0) {
				LoopConditionalNode loopNode = loopNodes.get(0);
				
				// Check if loop condition is evaluated before or after the loop branch
				if (!loopNode.hasAttribute("evaluateBefore"))
					throw new AnalysisException("evaluateBefore attribute not found in loop node");
				if (!loopNode.hasAttribute("branchNode"))
					throw new AnalysisException("branchNode attribute not found in loop node");				
				
				// Create construct
				if ((boolean)loopNode.getAttribute("evaluateBefore")) {
					constructWithPreEvaluation(g, loopNode);
				} else
					constructWithPostEvaluation(g, loopNode);
			}
		}
		return inputGraph;
	}
	
	private void constructWithPreEvaluation(Graph g, LoopConditionalNode loopNode) throws AnalysisException {
		// Get the end node of the loop branch
		Node branchEndNode = g.getNodeByName(loopNode.getAttribute("branchNode").toString());
		Node branchStartNode = null;
		
		List<Edge> outgoingEdges = g.getOutgoingEdges(loopNode, EdgeType.Control);
		if (outgoingEdges.size() == 0 || outgoingEdges.size() > 2)
			throw new AnalysisException("Loop node " + loopNode.getName() + " needs to have 2 outgoing edges, " + outgoingEdges.size() + " edges found");
		else if (outgoingEdges.size() == 1) {
			// Get possible branch start nodes and check if they are loop branches
			branchStartNode = outgoingEdges.get(0).getEnd();
			List<Node> visitedListn1 = new ArrayList<Node>();
			visitedListn1.add(loopNode);
			boolean n1IsLoopBranch = isLoopBranch(branchStartNode, branchEndNode, g, visitedListn1);
			
			if (!n1IsLoopBranch)
				throw new AnalysisException("No loop branch found");
		} else {
			// Check possibility 1
			Node n1 = outgoingEdges.get(0).getEnd();
			List<Node> visitedListn1 = new ArrayList<Node>();
			visitedListn1.add(loopNode);
			boolean n1IsLoopBranch = isLoopBranch(n1, branchEndNode, g, visitedListn1);
			
			// Check possibility 2
			Node n2 = outgoingEdges.get(1).getEnd();
			List<Node> visitedListn2 = new ArrayList<Node>();
			visitedListn2.add(loopNode);
			boolean n2IsLoopBranch = isLoopBranch(n2, branchEndNode, g, visitedListn2);
			
			// Make sure not both branches are loop branches
			if ((n1IsLoopBranch && n2IsLoopBranch) || (!n1IsLoopBranch && !n2IsLoopBranch))
				throw new AnalysisException("No loop branch found, or both branches are loop branches");
			
			// Select the loop branch start node
			branchStartNode = (n1IsLoopBranch) ? n1 : n2;			
		}
		
		// Create construct
		LoopConstruct construct = createLoopConstruct(g, loopNode, branchStartNode);
		
		// Add graphs to queue, for further identification of loop constructs (nested, or further along the path in the same graph)
		graphQueue.add(construct.getInnerGraph());
		graphQueue.add(g);		
	}
	
	private void constructWithPostEvaluation(Graph g, LoopConditionalNode loopNode) {
		// Get the start node of the loop branch
		Node branchStartNode = g.getNodeByName(loopNode.getAttribute("branchNode").toString());
		
		// Create construct
		LoopConstruct construct = createLoopConstruct(g, loopNode, branchStartNode);
		
		// Add graphs to queue, for further identification of loop constructs (nested, or further along the path in the same graph)
		graphQueue.add(construct.getInnerGraph());
		graphQueue.add(g);		
	}
	
	private LoopConstruct createLoopConstruct(Graph g, LoopConditionalNode loopNode, Node branchStartNode) {
		/**
		 * Construct creation
		 */
		LoopConstruct construct = new LoopConstruct("loop_" + loopNode.getName());
		construct.setConditionNode(loopNode);
		construct.setEvaluateConditionBefore((boolean)loopNode.getAttribute("evaluateBefore"));
		g.addNode(construct);
		
		/**
		 * Branch creation
		 */
		Graph loopBranch = new Graph();
		copyUntilConditionalNodeFound(branchStartNode, loopNode, loopBranch, g, new ArrayList<Node>());
		construct.setInnerGraph(loopBranch);
		
		/**
		 * Remove old nodes/edges
		 */
		g.removeEdge(g.findEdge(loopNode, branchStartNode, EdgeType.Control));
		g.removeNode(loopNode);		
		
		/**
		 * Update incoming/outgoing edges
		 */
		// Remove loop node from graph, remove loop edge (from loopcondition to branchstart), change incoming edges to loop branch and update outgoing edges of conditional loop node
		for (Edge e : g.getIncomingEdges(branchStartNode, EdgeType.Control))
			e.setEnd(construct);
		for (Edge e : g.getIncomingEdges(loopNode, EdgeType.Control))
			e.setEnd(construct);		
		for (Edge e : g.getOutgoingEdges(loopNode, EdgeType.Control))
			e.setStart(construct);
		
		return construct;
	}
	
	private void copyUntilConditionalNodeFound(Node curNode, LoopConditionalNode condNode, Graph newGraph, Graph lookupGraph, List<Node> visitedNodes) {
		/**
		 * Security check to infinite loops
		 */
		if (visitedNodes.contains(curNode))
			return;
		else
			visitedNodes.add(curNode);
		
		/**
		 * Move node to new graph
		 */
		lookupGraph.removeNode(curNode);
		newGraph.addNode(curNode);

		/**
		 * Consider outgoing edges. When not pointing to conditional loop node, move edge and continue walking
		 */
		// Walk through outgoing edges
		List<Edge> outgoingEdges = lookupGraph.getOutgoingEdges(curNode, EdgeType.Control);
		for (Edge e : outgoingEdges) {
			// Remove from old graph
			lookupGraph.removeEdge(e);
			
			if (e.getEnd() != condNode) {		
				newGraph.addEdge(e);
				// Continue copying
				copyUntilConditionalNodeFound(e.getEnd(), condNode, newGraph, lookupGraph, visitedNodes);
			}
				
		}
	}
	
	private boolean isLoopBranch(Node curNode, Node branchEndNode, Graph g, List<Node> visitedNodes) {
		// Make sure the algorithm will not walk infinite loops
		if (visitedNodes.contains(curNode)) return false;
		else visitedNodes.add(curNode);
		
		// If the current node equals the branch end node, the end node is found, so this is the loop branch
		if (curNode == branchEndNode)
			return true;		
		
		// Follow outgoing edges
		for (Edge e : g.getOutgoingEdges(curNode, EdgeType.Control))
			if (isLoopBranch(e.getEnd(), branchEndNode, g, visitedNodes))
				return true;
		
		return false;
	}
	
	
	public List<LoopConditionalNode> findLoopNodes(Graph g) {
		List<LoopConditionalNode> result = new ArrayList<LoopConditionalNode>();
		for (Node n : g.getNodes()) {
			if (n instanceof LoopConditionalNode)
				result.add((LoopConditionalNode)n);
		}
		return result;
	}
	
	
}
